[LOJ6079]-养猫（线性规划转费用流）

先做了 $志愿者招募$，一样的套路——线性规划转费用流。

先钦定所有时间吃东西，然后选一些时刻变成睡觉。$x_i = 0/1$ 表示 $i$ 时刻是否睡觉，是的话代价为 $s_i - e_i$。

可以列出不等式组：

$$x_1 + \cdots + x_{k} \geq ms$$ $$x_1 + \cdots + x_{k} \leq k - me$$ $$\cdots$$ $$x_{n - k + 1} + \cdots + x_n \leq k - me$$

变成标准型（就是不等号变等号）：

$$x_1 + \cdots + x_{k} = ms + y_1$$ $$x_1 + \cdots + x_{k} = k - me - z_1$$ $$\cdots$$ $$x_{n - k + 1} + \cdots + x_n = k - me - z_{n - k + 1}$$

线性规划转费用流要求每个变量恰好出现一次为正、一次为负，于是添加一个等式 $0 = 0$ 并两两做差：

$$x_1 + \cdots + x_{k} = ms + y_1$$ $$y_1 + z_1 = k - ms - me$$ $$x_{k + 1} + (k - ms - me) = x_1 + z_1 + y_2$$ $$\cdots$$ $$k - me = x_{n - k + 1} + \cdots + x_n + z_{n - k + 1}$$

这一类线性规划转费用流的建模方法，是把等式看作点，等式平衡对应网络流中的流量平衡。

那么每个变量看作流，为正则是入，为负则是出。从出的等式向入的等式连 $(cap, val)$ 的边。例如本题中 $x_i$ 连边为 $(1, s_i - e_i)$，而 $y_i$, $z_i$ 等辅助变量连边为 $(\infty, 0)$。

对于常数（设为 $c$）也要处理，为正则视为源点发出给你的，为负则视为你发出给汇点的：$(|c|, 0)$。

正确性怎么理解呢qwq？最大流跑完了，每个点的等式都被满足

回到本题，由于第一个等式的常数 $ms$ 在等式右边，我们把右边看作入，跑最大费用流就完事了。

$Code$